package cn.edu.xjtu.carlWay.array.searchRange;

/**
 * 34. 在排序数组中查找元素的第一个和最后一个位置
 * <p>
 * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
 * 如果数组中不存在目标值 target，返回[-1, -1]。
 * 进阶：
 * 你可以设计并实现时间复杂度为O(log n)的算法解决此问题吗？
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
    public static void main(String[] args) {
        Solution solu = new Solution();
        int[] nums = {1};
        solu.searchRange(nums, 1);
        System.out.println();
    }

    public int[] searchRange(int[] nums, int target) {
        int leftBorder = getLeftBorder(nums, target);
        int rightBorder = getRightBorder(nums, target);
        if (leftBorder == -1 || rightBorder == -1) {
            return new int[]{-1, -1};
        }
        if (leftBorder <= rightBorder)
            return new int[]{leftBorder, rightBorder};
//        System.out.println(leftBorder + " " + rightBorder);
        return new int[]{-1, -1};
    }

    private int getRightBorder(int[] nums, int target) {
        int rightBorder = -1;
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            if (nums[mid] <= target) {
                left = mid + 1;
                rightBorder = mid;
            } else {
                right = mid - 1;
            }
        }
        return rightBorder;
    }

    private int getLeftBorder(int[] nums, int target) {
        int leftBorder = -1;
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            if (nums[mid] >= target) {
                right = mid - 1;
                leftBorder = mid;
            } else {
                left = mid + 1;
            }
        }
        return leftBorder;
    }

}
